/**
 * //给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * //
 * //输入: nums = [1,1,1,2,2,3], k = 2
 * //输出: [1,2]
 * //
 * //
 * // 示例 2:
 * //
 * //
 * //输入: nums = [1], k = 1
 * //输出: [1]
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= nums.length <= 10⁵
 * // k 的取值范围是 [1, 数组中不相同的元素的个数]
 * // 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 * //
 * //
 * //
 * //
 * // 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 * // Related Topics 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列） 👍 956 👎 0
 */

package com.xixi.dataStructure.heap;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class ID00347TopKFrequentElements {
    public static void main(String[] args) {
        Solution solution = new ID00347TopKFrequentElements().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        class TopFrequent {
            public int frequency;
            public int val;

            public TopFrequent(int frequency, int val) {
                this.frequency = frequency;
                this.val = val;
            }


        }


        public int[] topKFrequent(int[] nums, int k) {
            //建立一个频率和val的对应关系
            Map<Integer, Integer> counts = new HashMap<>();
            for (int num : nums) {
                counts.put(num, counts.getOrDefault(num, 0) + 1);
            }

            //按照频率大小，构建一个小顶堆
            //An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering,
            //优先级队列是越小越靠前
            PriorityQueue<TopFrequent> topKFrequentQueue = new PriorityQueue<>(new Comparator<TopFrequent>() {
                @Override
                public int compare(TopFrequent q1, TopFrequent q2) {
                    return q1.frequency - q2.frequency;
                }
            }
            );
            for(Map.Entry<Integer, Integer> entry: counts.entrySet()){
                int frequency = entry.getValue();
                int val = entry.getKey();
                if(topKFrequentQueue.size() < k){
                    topKFrequentQueue.offer(new TopFrequent(frequency, val));
                }else{
                    if(topKFrequentQueue.peek().frequency < frequency){ //如果当前频率比最小的大，那就移除堆顶元素
                        topKFrequentQueue.poll();
                        topKFrequentQueue.offer(new TopFrequent(frequency,val));
                    }
                }


            }
            int[] result = new int[k];
            for (int i = 0; i < k; ++i) {
                result[i] = topKFrequentQueue.poll().val;
            }
            return result;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}